'''Created on Nov 16, 2009
   Finished on Nov 23, 2009
   
   Optimized on Apr 20,2010
   
# Problem Set 2 (Part IV)
# Name: Noah Spahn
# Collaborators: Dave Johannsen
# Time: 7:30'''
# Check this::: 
#    http://fupeg.blogspot.com/2008/04/diophantine-equation.html
#    www.math.utah.edu/~carlson/notes/python.pdf
#    http://www.wellho.net/solutions/python-python-list-python-tuple-python-dictionary.html
#    http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation
#    http://www.phys.uu.nl/~haque/computing/WPark_recipes_in_python.html
#    Dave Johannsen gave the best advice via code snippet

def solvDiophantine(sizes):
    list = []
    
    for quantity in range(0,600):
        list.append(quantity); 
        list[quantity]=0 # Initially assume we cannot buy this particular amount (quantity)
 
        for package in sizes:
        	if (quantity == package): # Can we order a package of this size?
        		list[quantity] = package  #If so, we start with a this size
        	elif ((quantity > package) and (list[quantity - package] > 0)):
						list[quantity] = package;  # Yes, we can buy a package of this size, plus whatever we needed to buy i-package pieces
    
    for i in range(0,len(list)): #loop over the list to find the last package you can't buy
        if list[i] == 0:
            y = i
    print "Given package sizes [",
    for item in sizes:
    	print '%d,'%item,
    print "] the largest number of McNuggets that cannot be bought in exact quantity is: %d"%y
    #print "List :",list

sets = ((6,9,20),(10,19,23),(10,29,30),(15,30,45))
for set in sets:
	solvDiophantine(set)